public class 合并两个有序数组_归并 {
    int[] tmp;
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        tmp = new int[n + m];
        for(int i = m;i < m + n;i++){
            nums1[i] = nums2[i - m];
        }
        mergeSort(nums1,0,nums1.length - 1);
    }

    private void mergeSort(int[] nums, int left, int right) {
        if(left >= right){
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid + 1,right);
        int cur1 = left;
        int cur2 = mid + 1;
        int i = 0;
        while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] < nums[cur2]){
                tmp[i++] = nums[cur1++];
            }else{
                tmp[i++] = nums[cur2++];
            }
        }
        while(cur1 <= mid){
            tmp[i++] = nums[cur1++];
        }
        while(cur2 <= right){
            tmp[i++] = nums[cur2++];
        }
        for (int j = left; j <= right; j++) {
            nums[j] = tmp[j - left];
        }
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}
